package taishan

import (
	"errors"
	"fmt"
	"gitee.com/tiger000/taishan_web/taishan/pathArray"
	"gitee.com/tiger000/taishan_web/taishan/routeRule"
	"sort"
	"strings"
	"sync"
)

const DepthMax = 22

type Node struct {
	middlewares []IMiddleware

	handler HandlerFunc //当前节点注册的handler

	//methodHandler map[string]HandlerFunc //GET POST 等对应的handler

	pattern string   // 待匹配路由，例如 /p/:lang
	part    []string // 路由中的一部分，例如 :lang

	//isWild      bool     // 是否精确匹配，part 含有 : 或 * 时为true
	topWildNode *Node     // 该节点的上层*节点 用于支持多个* 例如 /a/b/*/c/d/*/e
	nodeType    NodeTypes //节点类型 0 精确; 1 选项; 2 : 匹配一级; 3 * 匹配多级;
	depth       int       //节点深度，越深越优先 默认1
	weight      int64     //节点权重 = 当前节点depth*2^nodeType + 上一个节点权重
	children    []*Node   // 子节点，例如 [doc, tutorial, intro]

	//方法表
	methodGet     HandlerFunc
	methodHead    HandlerFunc
	methodPost    HandlerFunc
	methodPut     HandlerFunc
	methodDelete  HandlerFunc
	methodConnect HandlerFunc
	methodOptions HandlerFunc
	methodTrace   HandlerFunc
	methodPatch   HandlerFunc
	methodAll     HandlerFunc

	lock sync.Mutex //新增节点需要加锁
}

type NodeTypes uint8

const (
	_                             = iota
	NodeTypeMultiLevels NodeTypes = iota // 多级匹配 /a/*/b
	NodeTypeOneLevel                     // 一级匹配 /a/:/b
	NodeTypeOption                       //选项匹配，也是精确匹配 /a|b
	NodeTypePrecise                      //精确匹配 /a /a/b

)

// Len 节点排序接口实现
func (n *Node) Len() int {
	return len(n.children)
}

func (n *Node) Less(i, j int) bool {
	return n.children[i].nodeType < n.children[j].nodeType
}

func (n *Node) Swap(i, j int) {
	n.children[i], n.children[j] = n.children[j], n.children[i]
}

func (n *Node) sortAll() {
	if n.children != nil {
		for _, child := range n.children {
			child.sortAll()
		}
		sort.Sort(n)
	}

}

// PartToItems 路由规则转路由规则数组
func PartToItems(part string) []string {
	if part == ":" || part == "*" {
		return []string{part}
	}
	part = strings.Trim(part, "|")
	parts := strings.Split(part, "|")
	for i := 0; i < len(parts); i++ {
		if parts[i] == ":" || parts[i] == "*" || parts[i] == "" {
			parts = append(parts[0:i], parts[i+1:]...)
		}
	}
	sort.Slice(parts, func(i, j int) bool {
		return strings.Compare(parts[i], parts[j]) < 0
	})
	return parts
}

// PartsEq 比较两个路由规则数组
func PartsEq(parts1, parts2 []string) bool {
	if len(parts1) != len(parts2) {
		return false
	}
	for k, v := range parts1 {
		if v != parts2[k] {
			return false
		}
	}

	return true
}

// 第一个匹配成功的节点，用于插入
func (n *Node) matchChild(parts []string) *Node {
	//parts := PartToItems(part)
	for _, child := range n.children {
		if PartsEq(parts, child.part) {
			return child
		}
	}
	return nil
}

// 所有匹配成功的节点，用于查找
func (n *Node) matchChildren(part string) []*Node {
	nodes := make([]*Node, 0)

	//如果node是NodeTypeMultiLevels，并且是最后一个节点，则匹配所有
	if len(n.children) == 0 && n.nodeType == NodeTypeMultiLevels {
		nodes = append(nodes, n)
		return nodes
	}

	for _, child := range n.children {
		nodeMatched := false
		if child.nodeType == NodeTypeOneLevel || child.nodeType == NodeTypeMultiLevels {
			nodes = append(nodes, child)
			continue
		}
		for _, childPart := range child.part {
			if childPart == part {
				nodes = append(nodes, child)
				nodeMatched = true
			}
		}

		//*通配符，如果不匹配，回溯到*位置
		if !nodeMatched && child.topWildNode != nil {
			nodes = append(nodes, child.topWildNode)
		}

	}
	//重新排序
	/*sort.Slice(nodes, func(i, j int) bool {
		if nodes[i].depth > nodes[j].depth {
			return true
		} else if nodes[i].depth == nodes[j].depth && nodes[i].nodeType < nodes[j].nodeType {
			return true
		} else {
			return false
		}
	})*/

	return nodes
}

// 插入一条路由规则
// Deprecated
func (n *Node) insert(route string, parts routeRule.RouteRuleArray, height int, handler HandlerFunc) error {
	if len(parts) == height {
		if n.pattern != "" {
			return errors.New("路由冲突 " + n.pattern + " 和 " + route + " 路由一样")
		}
		n.pattern = routeRule.FormatRouteRule(parts)
		n.handler = handler
		return nil
	}

	part := parts[height]
	child := n.matchChild(part)
	if child == nil {
		items := part
		child = &Node{part: items, depth: height + 1}
		if len(items) > 1 {
			child.nodeType = NodeTypeOption
		} else if len(items) == 1 {
			if items[0] == ":" {
				child.nodeType = NodeTypeOneLevel
			} else if items[0] == "*" {
				child.nodeType = NodeTypeMultiLevels
				//关键
				child.topWildNode = child
			} else {
				child.nodeType = NodeTypePrecise
			}
		} else {
			return errors.New("非法内容:" + fmt.Sprintf("%v", part))
		}

		//关键
		if n.topWildNode != nil && child.nodeType != NodeTypeMultiLevels {
			child.topWildNode = n.topWildNode
		}
		child.weight = int64(child.nodeType)*1<<(DepthMax-child.depth) + n.weight
		n.children = append(n.children, child)
	}
	err := child.insert(route, parts, height+1, handler)
	if err != nil {
		return err
	}

	//插入后一定要排序
	sort.Slice(n.children, func(i, j int) bool {
		return n.children[i].nodeType < n.children[j].nodeType
	})

	return nil
}

func (n *Node) insertRoute(method, route string, handler HandlerFunc) error {
	parts, err := routeRule.Parse(route)
	if err != nil {
		return err
	}
	route = routeRule.FormatRouteRule(parts)
	return n.insertRouteAction(method, route, parts, 1, handler)
}

func (n *Node) insertRouteAction(method, route string, parts routeRule.RouteRuleArray, height int, handler HandlerFunc) error {
	if len(parts) == height {
		n.pattern = routeRule.FormatRouteRule(parts)
		return n.insertMethodHandler(method, handler)
	}

	part := parts[height]
	child := n.matchChild(part)
	if child == nil {
		items := part
		child = &Node{part: items, depth: height + 1}
		if len(items) > 1 {
			child.nodeType = NodeTypeOption
		} else if len(items) == 1 {
			if items[0] == ":" {
				child.nodeType = NodeTypeOneLevel
			} else if items[0] == "*" {
				child.nodeType = NodeTypeMultiLevels
				//关键
				child.topWildNode = child
			} else {
				child.nodeType = NodeTypePrecise
			}
		} else {
			return errors.New("非法内容:" + fmt.Sprintf("%v", part))
		}

		//关键
		if n.topWildNode != nil && child.nodeType != NodeTypeMultiLevels {
			child.topWildNode = n.topWildNode
		}

		child.weight = int64(child.nodeType)*1<<(DepthMax-child.depth) + n.weight

		//加锁
		n.children = append(n.children, child)

	}
	err := child.insertRouteAction(method, route, parts, height+1, handler)
	if err != nil {
		return err
	}

	//插入后一定要排序
	sort.Slice(n.children, func(i, j int) bool {
		return n.children[i].nodeType < n.children[j].nodeType
	})

	return nil
}
func (n *Node) updateRoute(method, route string, handler HandlerFunc) error {
	parts, err := routeRule.Parse(route)
	if err != nil {
		return err
	}
	route = routeRule.FormatRouteRule(parts)
	return n.updateRouteAction(method, route, parts, 1, handler)
}
func (n *Node) updateRouteAction(method, route string, parts routeRule.RouteRuleArray, height int, handler HandlerFunc) error {
	if len(parts) == height {
		n.pattern = routeRule.FormatRouteRule(parts)
		return n.updateMethodHandler(method, handler)
	}

	part := parts[height]
	child := n.matchChild(part)
	if child == nil {
		items := part
		child = &Node{part: items, depth: height + 1}
		if len(items) > 1 {
			child.nodeType = NodeTypeOption
		} else if len(items) == 1 {
			if items[0] == ":" {
				child.nodeType = NodeTypeOneLevel
			} else if items[0] == "*" {
				child.nodeType = NodeTypeMultiLevels
				//关键
				child.topWildNode = child
			} else {
				child.nodeType = NodeTypePrecise
			}
		} else {
			return errors.New("非法内容:" + fmt.Sprintf("%v", part))
		}

		//关键
		if n.topWildNode != nil && child.nodeType != NodeTypeMultiLevels {
			child.topWildNode = n.topWildNode
		}

		child.weight = int64(child.nodeType)*1<<(DepthMax-child.depth) + n.weight

		//加锁
		n.children = append(n.children, child)

	}
	err := child.updateRouteAction(method, route, parts, height+1, handler)
	if err != nil {
		return err
	}

	//插入后一定要排序
	sort.Slice(n.children, func(i, j int) bool {
		return n.children[i].nodeType < n.children[j].nodeType
	})

	return nil
}
func (n *Node) getMethodHandler(method string) HandlerFunc {
	switch method {
	case "GET":
		if n.methodGet != nil {
			return n.methodGet
		}
		return n.methodAll
	case "HEAD":
		if n.methodHead != nil {
			return n.methodHead
		}
		return n.methodAll
	case "POST":
		if n.methodPost != nil {
			return n.methodPost
		}
		return n.methodAll
	case "PUT":
		if n.methodPut != nil {
			return n.methodPut
		}
		return n.methodAll
	case "DELETE":
		if n.methodDelete != nil {
			return n.methodDelete
		}
		return n.methodAll
	case "CONNECT":
		if n.methodConnect != nil {
			return n.methodConnect
		}
		return n.methodAll
	case "OPTIONS":
		if n.methodOptions != nil {
			return n.methodOptions
		}
		return n.methodAll
	case "TRACE":
		if n.methodTrace != nil {
			return n.methodTrace
		}
		return n.methodAll
	case "PATCH":
		if n.methodPatch != nil {
			return n.methodPatch
		}
		return n.methodAll
	}
	return nil
}
func (n *Node) insertMethodHandler(method string, handler HandlerFunc) error {
	switch method {
	case "GET":
		if n.methodGet != nil {
			return errors.New(method + ":" + n.pattern + "路由冲突 ")
		}
		n.methodGet = handler
	case "HEAD":
		if n.methodHead != nil {
			return errors.New(method + ":" + n.pattern + "路由冲突 ")
		}
		n.methodHead = handler
	case "POST":
		if n.methodPost != nil {
			return errors.New(method + ":" + n.pattern + "路由冲突 ")
		}
		n.methodPost = handler
	case "PUT":
		if n.methodPut != nil {
			return errors.New(method + ":" + n.pattern + "路由冲突 ")
		}
		n.methodPut = handler
	case "DELETE":
		if n.methodDelete != nil {
			return errors.New(method + ":" + n.pattern + "路由冲突 ")
		}
		n.methodDelete = handler
	case "CONNECT":
		if n.methodConnect != nil {
			return errors.New(method + ":" + n.pattern + "路由冲突 ")
		}
		n.methodConnect = handler
	case "OPTIONS":
		if n.methodOptions != nil {
			return errors.New(method + ":" + n.pattern + "路由冲突 ")
		}
		n.methodOptions = handler
	case "TRACE":
		if n.methodTrace != nil {
			return errors.New(method + ":" + n.pattern + "路由冲突 ")
		}
		n.methodTrace = handler
	case "PATCH":
		if n.methodPatch != nil {
			return errors.New(method + ":" + n.pattern + "路由冲突 ")
		}
		n.methodPatch = handler
	case "ALL":
		if n.methodAll != nil {
			return errors.New(method + ":" + n.pattern + "路由冲突 ")
		}
		n.methodAll = handler
	}
	return nil
}
func (n *Node) updateMethodHandler(method string, handler HandlerFunc) error {
	switch method {
	case "GET":
		n.methodGet = handler
	case "HEAD":
		n.methodHead = handler
	case "POST":
		n.methodPost = handler
	case "PUT":
		n.methodPut = handler
	case "DELETE":
		n.methodDelete = handler
	case "CONNECT":
		n.methodConnect = handler
	case "OPTIONS":
		n.methodOptions = handler
	case "TRACE":
		n.methodTrace = handler
	case "PATCH":
		n.methodPatch = handler
	case "ALL":
		n.methodAll = handler
	}
	return nil
}

// 插入中间件
func (n *Node) insertMiddlewares(route string, middlewares ...IMiddleware) error {
	parts, err := routeRule.Parse(route)
	if err != nil {
		return err
	}
	route = routeRule.FormatRouteRule(parts)
	height := 1
	return n.insertMiddlewaresAction(route, parts, height, middlewares...)
}

func (n *Node) insertMiddlewaresAction(route string, parts routeRule.RouteRuleArray, height int, middlewares ...IMiddleware) error {
	if len(parts) == height {
		n.pattern = route
		n.middlewares = append(n.middlewares, middlewares...)
		return nil
	}

	part := parts[height]
	child := n.matchChild(part)
	if child == nil {
		n.lock.Lock()
		//双重验证
		child = n.matchChild(part)
		if child == nil {
			items := part
			child = &Node{part: items, depth: height + 1}
			if len(items) > 1 {
				child.nodeType = NodeTypeOption
			} else if len(items) == 1 {
				if items[0] == ":" {
					child.nodeType = NodeTypeOneLevel
				} else if items[0] == "*" {
					child.nodeType = NodeTypeMultiLevels
					//关键
					child.topWildNode = child
				} else {
					child.nodeType = NodeTypePrecise
				}
			} else {
				return errors.New("非法内容:" + fmt.Sprintf("%v", part))
			}

			//关键
			if n.topWildNode != nil && child.nodeType != NodeTypeMultiLevels {
				child.topWildNode = n.topWildNode
			}
			child.weight = int64(child.nodeType)*1<<(DepthMax-child.depth) + n.weight
			n.children = append(n.children, child)
		}
		n.lock.Unlock()

	}
	err := child.insertMiddlewaresAction(route, parts, height+1, middlewares...)
	if err != nil {
		return err
	}

	//插入后一定要排序
	sort.Slice(n.children, func(i, j int) bool {
		return n.children[i].nodeType < n.children[j].nodeType
	})

	return nil
}

// 更新中间件
func (n *Node) updateMiddlewares(route string, middlewares ...IMiddleware) error {
	parts, err := routeRule.Parse(route)
	if err != nil {
		return err
	}
	route = routeRule.FormatRouteRule(parts)
	height := 1
	return n.updateMiddlewaresAction(route, parts, height, middlewares...)
}
func (n *Node) updateMiddlewaresAction(route string, parts routeRule.RouteRuleArray, height int, middlewares ...IMiddleware) error {
	if len(parts) == height {
		n.pattern = route
		n.middlewares = middlewares
		return nil
	}

	part := parts[height]
	child := n.matchChild(part)
	if child == nil {
		n.lock.Lock()
		//双重验证
		child = n.matchChild(part)
		if child == nil {
			items := part
			child = &Node{part: items, depth: height + 1}
			if len(items) > 1 {
				child.nodeType = NodeTypeOption
			} else if len(items) == 1 {
				if items[0] == ":" {
					child.nodeType = NodeTypeOneLevel
				} else if items[0] == "*" {
					child.nodeType = NodeTypeMultiLevels
					//关键
					child.topWildNode = child
				} else {
					child.nodeType = NodeTypePrecise
				}
			} else {
				return errors.New("非法内容:" + fmt.Sprintf("%v", part))
			}

			//关键
			if n.topWildNode != nil && child.nodeType != NodeTypeMultiLevels {
				child.topWildNode = n.topWildNode
			}
			child.weight = int64(child.nodeType)*1<<(DepthMax-child.depth) + n.weight
			n.children = append(n.children, child)
		}
		n.lock.Unlock()

	}
	err := child.updateMiddlewaresAction(route, parts, height+1, middlewares...)
	if err != nil {
		return err
	}

	//插入后一定要排序
	sort.Slice(n.children, func(i, j int) bool {
		return n.children[i].nodeType < n.children[j].nodeType
	})

	return nil
}

// 通过path搜索
// @param height 从1开始
func (n *Node) search(pathParts pathArray.PathArray, height int) *Node {
	if len(pathParts) == height {
		if n.pattern == "" {
			return nil
		}
		return n
	}

	part := pathParts[height]
	children := n.matchChildren(part)

	for _, child := range children {
		result := child.search(pathParts, height+1)
		if result != nil {
			return result
		}
	}
	return nil
}

// 查询满足规则的所有路由节点
func (n *Node) searchAllNodes(pathParts pathArray.PathArray, height int, res *[]*Node) {
	if len(pathParts) == height {
		if n.pattern == "" {
			return
		}
		*res = append(*res, n)
		return
	}
	if n.nodeType == NodeTypeMultiLevels && len(n.children) == 0 {
		*res = append(*res, n)
		return
	}

	part := pathParts[height]
	children := n.matchChildren(part)

	for _, child := range children {
		child.searchAllNodes(pathParts, height+1, res)
	}
}

// 获取满足规则的所有路由节点
func (n *Node) getMatchedNodes(route string) (nodes []*Node, err error) {
	pathParts, err := pathArray.Parse(route)
	if err != nil {
		return nil, err
	}
	n.searchAllNodes(pathParts, 1, &nodes)

	//按照路由优先级排序
	/*sort.Slice(nodes, func(i, j int) bool {
		if nodes[i].depth < nodes[j].depth {
			return false
		} else if nodes[i].depth == nodes[j].depth && nodes[i].weight < nodes[j].weight {
			return false
		} else {
			return true
		}
	})*/
	return
}

// Print 打印路由
func (n *Node) Print(levels ...int) {
	var level int
	if len(levels) > 0 {
		level = levels[0]
	}
	if n != nil {
		fmt.Println(tab(level)+n.pattern, n.depth, n.weight)
		for _, child := range n.children {
			child.Print(level + 1)
		}
	} else {
		fmt.Println("routeNode:Nil")
	}

}

func tab(level int) string {
	s := ""
	for i := 0; i < level; i++ {
		//s += "\t"
		s += "----"
	}
	return s
}
